augmented_containers::​augmented_sequence_t

enum class augmented_sequence_physical_representation_e {
	rb3p,
	rb2p,
	finger_tree, };
enum class augmented_sequence_size_management_e {
	no_size,
	at_node_end,
	at_each_node_except_node_end,
};
template<
	typename element_t,
	typename allocator_t = std::allocator<element_t>,
	typename accumulator_t_ = augmented_sequence_helpers::empty_accumulator_t,
	typename augmented_sequence_physical_representation_t = std::integral_constant<augmented_sequence_physical_representation_e, augmented_sequence_physical_representation_e::rb3p>,
	typename augmented_sequence_size_management_t = std::integral_constant<augmented_sequence_size_management_e, augmented_sequence_size_management_e::at_each_node_except_node_end>
> struct augmented_sequence_t;

template<
	typename element_t,
	typename allocator_t,
	typename accumulator_t,
	typename augmented_sequence_physical_representation_t,
	typename augmented_sequence_size_management_t
> requires(static_cast<augmented_sequence_physical_representation_e>(augmented_sequence_physical_representation_t{}) == augmented_sequence_physical_representation_e::rb2p)
struct augmented_sequence_t;

template<
	typename element_t,
	typename allocator_t,
	typename accumulator_t,
	typename augmented_sequence_physical_representation_t,
	typename augmented_sequence_size_management_t
> requires(static_cast<augmented_sequence_physical_representation_e>(augmented_sequence_physical_representation_t{}) == augmented_sequence_physical_representation_e::rb3p)
struct augmented_sequence_t;

augmented_sequence_t is an augmented, general-purpose sequence. It's part of the augmented containers library, providing a stronger version of sequence containers (let containers (and possibly its subranges) always have several accompanying results of algorithms/views), as well as <algorithm> and <ranges> (when the input sequence changes, refresh output values/ranges in logarithmic time complexity).

• augmented_sequence_t allows subrange update: first modify some elements, then call update_range to refresh the accumulated results that cover those elements in O(distance(range)+lg(N)) time. A common mistake would be to forget to call update_range.
• augmented_sequence_t allows subrange query: call read_range to collect accumulated results that cover the range in O(lg(distance(range))) time. If the accumulated result is a range instead of a single value, the result is probably formed by accumulated results linking to each other, in this case you should not call read_range because there are no more pointers left for you to form another range (see examples below for an intuitive feel).
• augmented_sequence_t allows inserting and erasing single element in O(lg(N)) time. Inserting a range of elements is implemented by 1 bulk loading operation (O(distance(range)) time) and 1 split operation followed by 2 concatenate operations. Erasing a range of elements is implemented by 2 split operations.
• augmented_sequence_t allows spliting one sequence into two in O(lg(N)) time, and allows concatenating two sequences into one in O(lg(max(N_lhs, N_rhs))) time.
• ⚠Insert, erase, split, concatenate operations automatically update accumulated results of the affected nodes. update_range is needed only after modification of elements through dereferencing iterators.

Physical representations and Size management

Examples

The untagged pointers are drawn as solid lines. The 0b1-tagged pointers are drawn as dashed lines.

In rb3p's examples, end node's child_right, parent and child_left are drawn separately to not break graphviz's layout.

In rb2p's examples, non-end node's loop (node's my_list_beign() → node's child_right, node's child_right's next() → node's leftmost_descendent_of_child_right, node's leftmost_descendent_of_child_right's my_list_begin() → node's rightmost_descendent_of_child_left, node's rightmost_descendent_of_child_left's my_list_beign() → node's child_left, node's child_left's next() → node, the last edge of the loop is 0b1-tagged) has it's edges drawn end-to-end to make it clearer (the pointers are still pointing to whole nodes, not members of nodes).

In rb2p's examples, end node's loop (end node's my_list_beign() → leftmost_descendent_of_root, leftmost_descendent_of_root's my_list_beign() → root, root's next() → rightmost_descendent_of_root, rightmost_descendent_of_root's my_list_beign() → end_node, the last edge of the loop is 0b1-tagged) is not drawn to not break graphviz's layout.

In rb2p's examples, end node has my_list_beign_, non-end node has my_list_beign_ and next_. The bit210 of my_list_beign_ stores the role of the node (there are 8 roles: end△, root▽, child_left_not_a_leftmost_descendent◤, child_left_leftmost_descendent_of_non_root◢, child_left_leftmost_descendent_of_root◁, child_right_not_a_rightmost_descendent◥, child_right_rightmost_descendent_of_non_root◣, child_right_rightmost_descendent_of_root▷), the other bits are used to store my_list_beign(). The bit2 of next_ stores the color of the node (reflected on the color of cells' borders), the bit1 of next_ stores whether my_list_beign() is 0b1-tagged, the bit0 of next_ stores whether next() is 0b1-tagged, the other bits are used to store next().

empty

The accumulation step is skipped. What's left (when augmented_sequence_size_management_t is augmented_containers​::​augmented_sequence_size_management_e​::​at_each_node_except_node_end) can be seen as a std::vector/std::deque that supports fast split/concatenate and never invalidates iterators/references/pointers, or a std::list with random access ability.

augmented_containers::augmented_sequence_t<
	char,
	std::allocator<char>,
	augmented_containers::augmented_sequence_helpers::empty_accumulator_t,
	...
> augmented_sequence;

accumulator_yield_one_value

element_t(char)s are accumulated into accumulated_storage_t(std::string)s.

augmented_containers::augmented_sequence_t<
	char,
	std::allocator<char>,
	augmented_containers::augmented_sequence_helpers::accumulator_sequence_t<char, std::string>,
	...
> augmented_sequence;

accumulator_yield_multiple_values

element_t(int)s' addresses and arrays thereof are accumulated into their std::ranges::merge | std::views::take(3) (stores addresses so you can modify the original elements).

augmented_containers::augmented_sequence_t<
	int,
	std::allocator<int>,
	augmented_containers::augmented_sequence_helpers::accumulator_wrapping_accumulating_binary_functor_t<accumulating_min_n_element_binary_functor_t<int, 3, true>>,
	...
> augmented_sequence;

accumulator_yield_one_view

Each element_t(int)'s corresponding accumulated_storage_t comes with the navigator portion (prev and next pointers) to be ready to form a circular doubly linked list. The accumulator takes chunk-begins (std::ranges::prev(it).is_end() || (*std::ranges::prev(it) < 50) != (*it < 50)), discards non-chunk-begins (and takes other accumulated circular doubly linked lists), accumulates them into a circular doubly linked lists representing std::ranges::chunk_by_view of the original sequence.

augmented_containers::augmented_sequence_t<
	int,
	std::allocator<int>,
	diffing_adjacent_element_accumulator_t,
	...
> augmented_sequence;

accumulator_yield_multiple_views

Similar to the accumulator_yield_one_view example, except that each accumulated_storage_t has "a map from element % 3 to circular doubly linked list's end node" (instead of just "one end node"). The result represents C++32's std::ranges::group_by_view of the original sequence (navigator_style = std::ranges::group_by_view::navigator_style_t::circular_doubly_linked_list, map_container_tt = std::map).

augmented_containers::augmented_sequence_t<
	int,
	std::allocator<int>,
	group_by_element_accumulator_t,
	...
> augmented_sequence;

find_by_monotonic_predicate

element_t(std::string)s' .size()s are accumulated by std::size_t operator+(std::size_t, std::size_t). Use .find_by_monotonic_predicate([&](){ ... }) to find the first element where the accumulated_storage_t(std::size_t) (accumulated string size so far) starts to be greater than the given character index, i.e., the element that contains the the given character indexth character. Note that the hierarchical structure saves time by skiping substructures that don't contain the results.

augmented_containers::augmented_sequence_t<
    std::string,
    std::allocator<std::string>,
    augmented_containers::augmented_sequence_helpers::accumulator_wrapping_accumulating_binary_functor_t<accumulating_binary_functor_string_length>,
	...
> augmented_sequence;

find_by_heap_predicate

element_t(int)s are accumulated into their std::ranges::max. Use .find_by_heap_predicate(jts_output, [&](){ ... }) to eagerly find all elements greater than or equal to the given threshold. Note that the hierarchical structure saves time by skiping substructures that don't contain the results. It's possible to parallelize the search, depending on the availability of std::execution.

augmented_containers::augmented_sequence_t<
    int,
    std::allocator<int>,
    augmented_containers::augmented_sequence_helpers::accumulator_wrapping_accumulating_binary_functor_t<augmented_containers::augmented_sequence_helpers::accumulating_binary_functor_wrapping_homogeneous_binary_functor_t<int, augmented_containers::augmented_sequence_helpers::max_t<int>>>,
	...
> augmented_sequence;

find_by_heap_predicate_generator

element_t(int)s are accumulated into their std::ranges::max. Use .find_by_heap_predicate_generator([&](){ ... }) to lazily iterate through elements greater than or equal to the given threshold, until an element divisible by the given denominator is encountered. Note that the hierarchical structure saves time by skiping substructures that don't contain the results. It's possible to parallelize the search, depending on the availability of std::execution.

augmented_containers::augmented_sequence_t<
    int,
    std::allocator<int>,
    augmented_containers::augmented_sequence_helpers::accumulator_wrapping_accumulating_binary_functor_t<augmented_containers::augmented_sequence_helpers::accumulating_binary_functor_wrapping_homogeneous_binary_functor_t<int, augmented_containers::augmented_sequence_helpers::max_t<int>>>,
	...
> augmented_sequence;